On the performance of the ICP algorithm

We present upper and lower bounds for the number of iterations performed by the Iterative Closest Point (ICP) algorithm. This algorithm has been proposed by Besl and McKay as a successful heuristic for matching of point sets in d-space under translation, but so far it seems not to have been rigorously analyzed. We consider two standard measures of resemblance that the algorithm attempts to optimize: The RMS (root mean squared distance) and the (one-sided) Hausdorff distance. We show that in both cases the number of iterations performed by the algorithm is polynomial in the number of input points. In particular, this bound is quadratic in the one-dimensional problem, under the RMS measure, for which we present a lower bound construction of Ω(nlogn) iterations, where n is the overall size of the input. Under the Hausdorff measure, this bound is only O(n) for input point sets whose spread is polynomial in n, and this is tight in the worst case.We also present several structural geometric properties of the algorithm under both measures. For the RMS measure, we show that at each iteration of the algorithm the cost function monotonically and strictly decreases along the vector Δt of the relative translation. As a result, we conclude that the polygonal path π, obtained by concatenating all the relative translations that are computed during the execution of the algorithm, does not intersect itself. In particular, in the one-dimensional problem all the relative translations of the ICP algorithm are in the same (left or right) direction. For the Hausdorff measure, some of these properties continue to hold (such as monotonicity in one dimension), whereas others do not.     

Finding more perfect matchings in leapfrog fullerenes

We use some recent results on the existence of long cycles in leapfrog fullerenes to establish new exponential lower bounds on the number of perfect matchings in such graphs. The new bounds are expressed in terms of Fibonacci numbers.     

GLOBAL SUPERCONVERGENCES OF THE DOMAIN DECOMPOSITION METHODS WITH NONMATCHING GRIDS

1. IlltroductionA nonconforming domain decomposition method with Lagrangian multipliers was proposedin [13]. The basic idea of this method is to deal with the nonconforming of nonmatching gridsby illtroducing the Lagrangian multipliers on interfaces of subdomains and its advalltages arethat it allows not only the incompatibility of the internal variables on the interface betweensubdomains, but also the discolltinuity of the boundary variables on the common venices ofsubdomains. Thus one can c…     

q-Weighted log-concavity and q-product theorem on the normality of posets

We show that q-weighted log-concavity and the strict normalized matching property are preserved under the q-direct product over weighted posets. As consequences, two classes of weighted posets including the finite linear lattices are strictly q-weighted log-concave and strictly normal.     

Minimally non-Pfaffian graphs

We consider the question of characterizing Pfaffian graphs. We exhibit an infinite family of non-Pfaffian graphs minimal with respect to the matching minor relation. This is in sharp contrast with the bipartite case, as Little [C.H.C. Little, A characterization of convertible (0,1)-matrices, J. Combin. Theory Ser. B 18 (1975) 187–208] proved that every bipartite non-Pfaffian graph contains a matching minor isomorphic to K_3,3. We relax the notion of a matching minor and conjecture that there are only finitely many (perhaps as few as two) non-Pfaffian graphs minimal with respect to this notion.We define Pfaffian factor-critical graphs and study them in the second part of the paper. They seem to be of interest as the number of near perfect matchings in a Pfaffian factor-critical graph can be computed in polynomial time. We give a polynomial time recognition algorithm for this class of graphs and characterize non-Pfaffian factor-critical graphs in terms of forbidden central subgraphs.     

FTRLIM: Distributed Instance Matching Framework for Large-Scale Knowledge Graph Fusion

Instance matching is a key task in knowledge graph fusion, and it is critical to improving the efficiency of instance matching, given the increasing scale of knowledge graphs. Blocking algorithms selecting candidate instance pairs for comparison is one of the effective methods to achieve the goal. In this paper, we propose a novel blocking algorithm named MultiObJ, which constructs indexes for instances based on the Ordered Joint of Multiple Objects’ features to limit the number of candidate instance pairs. Based on MultiObJ, we further propose a distributed framework named Follow-the-Regular-Leader Instance Matching (FTRLIM), which matches instances between large-scale knowledge graphs with approximately linear time complexity. FTRLIM has participated in OAEI 2019 and achieved the best matching quality with significantly efficiency. In this research, we construct three data collections based on a real-world large-scale knowledge graph. Experiment results on the constructed data collections and two real-world datasets indicate that MultiObJ and FTRLIM outperform other state-of-the-art methods.     

Temperature dependent narrow-band terahertz pulse generation in periodically poled crystals via difference frequency generation

Femtosecond optical pulse is used to generate narrow-band terahertz pulses depending on a quasi-phase-matched condition in periodically poled lithium niobate (PPLN) and stoichiometric lithium tantalate (PPSLT) crystals by difference frequency generation. The origin of narrow-band THz generation proved that the two frequency components of the fs pulse contribute to the frequency mixing. By cryogenic cooling, the absorption of THz waves in the crystal is significantly reduced which results in efficient THz generation. Simultaneously generated forward and backward THz pulses were 1.38 and 0.65 THz with as narrow as the bandwidth of 32 GHz in the PPSLT sample. Temperature dependence of the generated THz waveforms had good agreement with the simulation result using one dimensional plane-wave propagation model.     

基于溴钨灯和LED积分球光源的可调谐光谱分布及光谱匹配

采用溴钨灯和恒流驱动的LED混合作为积分球内部光源,提出了模拟退火算法作为光谱匹配算法,研究了光谱分布可调谐积分球光源的光谱匹配技术.仿真实验表明,该混合光源完全能够定量地模拟CIE-D65和等能光谱分布,且在辐射功率优于LED模拟结果的前提下,LED的数量分别减少79.8％和82.9％,平均相对误差分别减小10％和4...     

求解波束波导中激励-传输-辐射问题的积分方程方法

针对波束波导系统结构和馈电特性,应用体面积分方程建立了任意结构波束波导中电磁波的激励、传输和辐射问题所对应的物理模型.在激励端,采用模式展开方法描述输入口面场分布,并利用模式匹配方法精确模拟波束波导馈电端的匹配状况.通过对波束波导内部的实际结构的精确拟合,基于积分方程建立了激励-传输-辐射的电磁模型,并以高效数值解法给...     

应用于地形匹配导航的激光高度计设计

为解决基于雷达高度表探测的地形匹配导航系统探测精度不高、易受电子干扰影响而失效、且在跨海飞行时无法导航的难题,设计了一种激光高度计来代替雷达高度表进行地形探测。采用二极管泵浦固体激光器技术设计激光发射装置,输出近红外/蓝绿双波长激光,既可以测量陆地地形高度,又可以穿透海水探测海底地形;并根据激光高度计拟达到的性能指标选择合适的光电探测器,优化设计了光学系统、扫描系统和信号处理系统。所设计的激光高度计具有体积小、重量轻、高重频、探测灵敏度高、抗电磁干扰能力强等特点。